第38章 算法的复杂度评估

算法的复杂度是衡量算法效率的重要指标，主要包括时间复杂度和空间复杂度。时间复杂度用于描述算法执行所需的时间与输入规模之间的关系，空间复杂度则用于描述算法执行过程中所需要的存储空间与输入规模之间的关系。评估算法的复杂度是选择和优化算法的基础。

38.1 算法复杂度的基本概念

1. 算法：解决特定问题的步骤和方法，同一问题可以存在多种不同实现。
2. 输入规模：一般用 $n$ 表示，代表待处理数据总量，例如数组长度、矩阵行列数等。
3. 复杂度函数
   • $T(n)$：时间消耗函数，描述输入规模为 $n$ 时的操作次数；
   • $S(n)$：空间消耗函数，描述输入规模为 $n$ 时额外占用内存；
4. 渐近复杂度：只关注 $n$ 趋近无穷大时函数的增长趋势，忽略常数、低次项，使用大O符号表示。

38.2 时间复杂度

38.1 大O符号定义

记为 $O(f(n))$，含义：存在常数 $c>0$、$n_0$，当 $n \ge n_0$ 时，满足 $T(n) \le c \cdot f(n)$，代表算法运行时间的上界。

38.2 化简规则

1. 舍弃常数项：$O(2n+5) \Rightarrow O(n)$；
2. 舍弃低次项：$O(n^2 + 10n + 7) \Rightarrow O(n^2)$；
3. 舍弃常数系数：$O(5\log n) \Rightarrow O(\log n)$；
4. 嵌套循环复杂度相乘，顺序代码取最高阶复杂度。

38.3 常见复杂度（增速由慢到快）

$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$

38.4 代码分析示例

1. 常数阶 $O(1)$

int getFirst(int arr[], int n) {
    return arr[0];
}

仅单次操作，与数据规模无关。

2. 线性阶 $O(n)$

int sum(int arr[], int n) {
    int s = 0;
    for(int i = 0; i < n; i++) s += arr[i];
    return s;
}

单层循环，执行 $n$ 次。

3. 平方阶 $O(n^2)$（冒泡排序）

void bubble(int arr[], int n) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n-i-1; j++) {
            if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
        }
    }
}

两层嵌套循环，总操作约 $n^2$。

4. 对数阶 $O(\log n)$（二分查找）

int binSearch(int arr[], int n, int target) {
    int l = 0, r = n-1;
    while(l <= r) {
        int mid = l + (r-l)/2;
        if(arr[mid]==target) return mid;
        else if(arr[mid]<target) l = mid+1;
        else r = mid-1;
    }
    return -1;
}

每次区间减半，循环次数为 $\log_2 n$。

38.3 空间复杂度

38.1 定义与规则

空间复杂度 $S(n)$ 描述算法额外开辟的临时空间大小，输入数据占用空间不计入。化简规则与时间复杂度一致。

38.2 常见空间类型

• $O(1)$：仅固定常数临时变量；
• $O(n)$：开辟长度为 $n$ 的数组；
• $O(n^2)$：$n \times n$ 二维数组；
• 递归空间：等于递归最大深度。

38.3 示例

1. $O(1)$ 空间（原地交换）

void swap(int &a, int &b) {
    int t = a; a = b; b = t;
}

2. $O(n)$ 空间（复制数组）

int* copy(int arr[], int n) {
    int* p = new int[n];
    for(int i=0;i<n;i++) p[i]=arr[i];
    return p;
}

3. 递归 $O(n)$（阶乘）

int fac(int n) {
    if(n <= 1) return 1;
    return n * fac(n-1);
}

递归深度为 $n$，栈空间消耗 $O(n)$。

38.4 时空权衡

多数场景可通过空间换时间、时间换空间：

1. 空间换时间：哈希表存储数据，查找从 $O(n)$ 降到 $O(1)$；
2. 时间换空间：DP滚动数组，二维 $O(n^2)$ 压缩为一维 $O(n)$，仅少量增加遍历开销。

38.5 最好、最坏、平均复杂度

1. 最好情况：输入最优，操作最少（如有序数组冒泡排序仅一轮遍历，$O(n)$）；
2. 最坏情况：输入最差，操作最多，工业评估标准；
3. 平均情况：所有输入概率平均后的复杂度；

38.6 分析注意事项

1. 小规模数据（$n<100$）复杂度差异感知不明显；
2. 递归算法必须计入调用栈空间；
3. 复杂度仅描述增长趋势，不能直接对应程序运行毫秒；